#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1010;

int dis[N], pre[N], preve[N];  
int n, m;

struct edge {
    int to, cost, capacity, rev;
    edge(int to_, int cost_, int c, int rev_) {
        to = to_;
        cost = cost_;
        capacity = c;
        rev = rev_;
    }
};

vector<edge> e[N]; 
void addedge(int from, int to, int cost, int capacity) {
    e[from].push_back(edge(to, cost, capacity, e[to].size()));
    e[to].push_back(edge(from, -cost, 0, e[from].size() - 1));
}

bool spfa(int s, int t, int cnt){//套用SPFA模板
    bool inq[N];
    memset(pre, -1, sizeof(pre));
    for(int i = 1; i <= cnt; ++i){ dis[i] = INF; inq[i] = false; }
    dis[s] = 0;
    queue <int> Q;
    Q.push(s);
    inq[s] = true;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        for(int i=0; i<e[u].size(); i++)
            if(e[u][i].capacity>0){
                int v = e[u][i].to, cost = e[u][i].cost;
                if(dis[u]+cost < dis[v]){
                    dis[v] = dis[u]+cost;
                    pre[v] = u;       
                    preve[v] = i;    
                    if(!inq[v]){
                        inq[v] = true;
                        Q.push(v);
                    }
                }
            }
    }
    return dis[t] != INF;       
}
int mincost(int s, int t, int cnt){ 
    int cost = 0;
    while(spfa(s,t,cnt)){
        int v = t, flow = INF;   
        while(pre[v] != -1){  
            int u = pre[v], i = preve[v];  
            flow = min(flow, e[u][i].capacity); 
            v = u;                  
        }
        v = t;
        while(pre[v] != -1){
            int u = pre[v], i = preve[v];
            e[u][i].capacity -= flow;        
            e[v][e[u][i].rev].capacity += flow; 
            v = u;                 
        }
        cost += dis[t] * flow; 
    }
    return cost;                                
}
int main(){
    while(~scanf(" %d %d", &n, &m)){
        for(int i=0;i<N; i++)  e[i].clear();  
        for(int i=1;i<=m;i++){
            int u,v,w; scanf(" %d %d %d",&u,&v,&w);
            addedge(u,v,w,1);addedge(v,u,w,1);
		}
		int s = n+1,t=n+2;
		addedge(s,1,0,2);
		addedge(n,t,0,2);
		printf("%d\n",mincost(s,t,n+2));
	}
	return 0;
}